package org.liaohailong.helloworld;

import androidx.annotation.NonNull;
import androidx.annotation.Nullable;

/**
 * Author: liaohailong
 * Time: 2021/4/25 20:31
 * Describe:
 */
public class BSTree<E extends Comparable<E>> {
    private Node<E> root;

    public void add(E e) {
        root = add(root, e);
    }

    public Node<E> add(Node<E> node, E e) {
        if (node == null) {
            return new Node<>(e, null, null);
        }
        int compare = e.compareTo(node.key);
        if (compare < 0) {
            node.left = add(node.left, e);
        } else if (compare > 0) {
            node.right = add(node.right, e);
        } else {
            node.key = e;
        }
        return node;
    }

    public Node<E> find(E e) {
        return find(root, e);
    }

    private Node<E> find(Node<E> node, E e) {
        if (node == null) return null;
        int compare = e.compareTo(node.key);
        if (compare < 0) {
            return find(node.left, e);
        } else if (compare > 0) {
            return find(node.right, e);
        } else {
            return node;
        }
    }

    public void remove(Node<E> node) {
        root = remove(root, node);
    }

    private Node<E> remove(Node<E> root, Node<E> node) {
        int compare = node.compareTo(root);
        if (compare < 0) {
            root.left = remove(root.left, node);
        } else if (compare > 0) {
            root.right = remove(root.right, node);
        } else {
            // 仅剩余单个节点，直接返回上一级拼接
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            // 转换右侧节点
            Node<E> temp = root;
            Node<E> min = min(root.right); // 最小值节点
            min.right = removeMin(root.right); // 最小值节点的右侧子节点，赋值给它上一级节点的左节点
            min.left = temp.left;// 移除节点的左侧节点，交给新晋节点左侧，连接起左侧所有节点
            root = min;
        }
        return root;
    }

    private Node<E> removeMin(Node<E> node) {
        if (node.left == null) return node.right;
        node.left = removeMin(node);
        return node;
    }

    private Node<E> min(Node<E> node) {
        while (node.left != null) node = node.left;
        return node;
    }

    public static final class Node<E extends Comparable<E>> {
        E key;

        Node<E> left;
        Node<E> right;

        public Node(@NonNull E key,
                    @Nullable Node<E> left,
                    @Nullable Node<E> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }

        public int compareTo(Node<E> other) {
            return key.compareTo(other.key);
        }

        public int compareTo(E other) {
            return key.compareTo(other);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
